🔀 두 정렬 리스트 병합하기

이미 정렬된 두 리스트를 하나의 정렬된 리스트로 합치는 문제로, Merge Sort의 핵심 단계이기도 합니다.

1️⃣ 문제 접근

• 두 리스트의 맨 앞 원소를 비교해, 더 작은 쪽을 결과 리스트에 추가하고 해당 포인터를 한 칸 이동
• 한쪽 리스트가 먼저 끝나면, 남은 리스트를 그대로 결과 뒤에 이어 붙임
• 전체를 다시 정렬할 필요 없이 각 리스트를 한 번씩만 순회하면 되므로 O(n + m)

2️⃣ 풀이 코드

function mergeSortedLists(a, b) {
  const result = [];
  let i = 0, j = 0;

  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }

  return [...result, ...a.slice(i), ...b.slice(j)];
}

mergeSortedLists([1, 3, 5], [2, 4, 6]); // [1, 2, 3, 4, 5, 6]

• Merge Sort는 배열을 계속 반으로 나눈 뒤, 이 병합 과정을 재귀적으로 반복해 전체를 정렬하는 알고리즘

✍️ 한 줄 정리

두 정렬 리스트 병합은 각 리스트의 포인터를 하나씩 비교하며 진행해 O(n+m)에 처리할 수 있고, 이 과정을 재귀적으로 반복한 것이 Merge Sort다.